package com.itzmn.newcode.offer;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/17 14:45
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  剑指Offer  判断一个二叉树是否是平衡二叉树
 *
 *  思路，
 *
 *   没做出来
 */
public class IsBalanceBinTree {


    public static void main(String[] args) {

        new IsBalanceBinTree().init();
    }

    public void init(){

        TreeNode tree = createTree(new int[]{1, 2, 3, 4, 5, 6, 7});
    }
    /**
     * 创建二叉树
     * @param arrs
     * @return
     */
    public TreeNode createTree(int[] arrs){

        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        for (int i:arrs){
            treeNodes.add(new TreeNode(i));
        }
        TreeNode root = treeNodes.get(0);

        for (int i = 0; i < arrs.length/2; i++) {
            if (i*2+1<arrs.length){
                treeNodes.get(i).left=treeNodes.get(i*2+1);
            }
            if(i*2+2<treeNodes.size()){//避免偶数的时候 下标越界
                treeNodes.get(i).right=treeNodes.get(i*2+2);
            }
        }

        return root;

    }

    public boolean IsBalanced_Solution(TreeNode root) {

        ArrayList<Integer> integers = new ArrayList<>();
        if (root == null){
            return false;
        }

        zhognxu(integers,root);
        for (int i=0;i<integers.size()-1;i++){
            if (integers.get(i)>=integers.get(i+1)){
                return false;
            }
        }
        return true;

    }

    /**
     *
     * @param arrs
     * @param root
     */
    public void zhognxu(ArrayList<Integer> arrs,TreeNode root){

        if (root.left != null){
            zhognxu(arrs,root.left);
        }
        arrs.add(root.val);
        if (root.right != null){
            zhognxu(arrs,root.right);
        }

    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

}
